{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Swap Adjacent in LR String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canTransform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在LR字符串中交换相邻字符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个由 <code>&#39;L&#39;</code> , <code>&#39;R&#39;</code> 和 <code>&#39;X&#39;</code> 三个字符组成的字符串（例如<code>&quot;RXXLRXRXL&quot;</code>）中进行移动操作。一次移动操作指用一个<code>&quot;LX&quot;</code>替换一个<code>&quot;XL&quot;</code>，或者用一个<code>&quot;XR&quot;</code>替换一个<code>&quot;RX&quot;</code>。现给定起始字符串<code>start</code>和结束字符串<code>end</code>，请编写代码，当且仅当存在一系列移动操作使得<code>start</code>可以转换成<code>end</code>时， 返回<code>True</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 :</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> start = &quot;RXXLRXRXL&quot;, end = &quot;XRLXXRRLX&quot;\n",
    "<strong>输出:</strong> True\n",
    "<strong>解释:</strong>\n",
    "我们可以通过以下几步将start转换成end:\n",
    "RXXLRXRXL -&gt;\n",
    "XRXLRXRXL -&gt;\n",
    "XRLXRXRXL -&gt;\n",
    "XRLXXRRXL -&gt;\n",
    "XRLXXRRLX\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= len(start) = len(end) &lt;= 10000</code>。</li>\n",
    "\t<li><code>start</code>和<code>end</code>中的字符串仅限于<code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>和<code>&#39;X&#39;</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [swap-adjacent-in-lr-string](https://leetcode.cn/problems/swap-adjacent-in-lr-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [swap-adjacent-in-lr-string](https://leetcode.cn/problems/swap-adjacent-in-lr-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"RXXLRXRXL\"\\n\"XRLXXRRLX\"', '\"X\"\\n\"L\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i < n and j < n:\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                c = start[i]\n",
    "                if c == 'L' and i < j or c == 'R' and i > j:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "        while i < n:\n",
    "            if start[i] != 'X':\n",
    "                return False\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            if end[j] != 'X':\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i < n and j < n:\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                c = start[i]\n",
    "                if (c == 'L' and i < j) or (c == 'R' and i > j):\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "        while i < n:\n",
    "            if start[i] != 'X':\n",
    "                return False\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            if end[j] != 'X':\n",
    "                return False\n",
    "            j += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        i = j = 0\n",
    "        while i < len(start) and j < len(end):\n",
    "            while i < len(start) and start[i] == 'X':\n",
    "                i += 1\n",
    "\n",
    "            while j < len(end) and end[j] == 'X':\n",
    "                j += 1\n",
    "\n",
    "            if i == len(start) or j == len(end):\n",
    "                break\n",
    "\n",
    "            if start[i] != end[j]:\n",
    "                return False\n",
    "\n",
    "            if (start[i] == 'L' and i < j) or (start[i] == 'R' and i > j):\n",
    "                return False\n",
    "\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        while i < len(start):\n",
    "            if start[i] != 'X':\n",
    "                return False\n",
    "            i += 1\n",
    "            \n",
    "        while j < len(end):\n",
    "            if end[j] != 'X':\n",
    "                return False\n",
    "            j += 1\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i < n and j < n:\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                c = start[i]\n",
    "                if c == 'L' and i < j or c == 'R' and i > j:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "        while i < n:\n",
    "            if start[i] != 'X':\n",
    "                return False\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            if end[j] != 'X':\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start.replace(\"X\", \"\") != end.replace(\"X\", \"\"):\n",
    "            return False\n",
    "        numl, numr = 0, 0\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == \"L\":\n",
    "                numl -= 1\n",
    "            elif start[i] == \"R\":\n",
    "                numr += 1\n",
    "            if end[i] == 'L':\n",
    "                numl += 1\n",
    "            elif end[i] == 'R':\n",
    "                numr -= 1\n",
    "            if numl < 0 or numr < 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start.replace('X', '') != end.replace('X', ''):\n",
    "            return False\n",
    "        j = 0\n",
    "        for i, c in enumerate(start):\n",
    "            if c == 'X': continue\n",
    "            while end[j] == 'X': \n",
    "                j += 1\n",
    "            if i != j and (c == 'L') == (i < j):\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while 1:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i >= n and j >= n:\n",
    "                return True\n",
    "            if i >= n or j >= n or start[i] != end[j]:\n",
    "                return False\n",
    "            if start[i] == 'L' and i < j:\n",
    "                return False\n",
    "            if start[i] == 'R' and i > j:\n",
    "                return False\n",
    "            i, j = i + 1, j + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < n or j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "\n",
    "            if i == n and j == n:\n",
    "                return True\n",
    "\n",
    "            if i == n or j == n or start[i] != end[j]:\n",
    "                return False\n",
    "\n",
    "            if start[i] == 'R' and i > j:\n",
    "                return False\n",
    "\n",
    "            if start[i] == 'L' and i < j:\n",
    "                return False\n",
    "\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i=j=0\n",
    "        while i<n and j<n:\n",
    "            while i<n and start[i]=='X':\n",
    "                i+=1\n",
    "            while j<n and end[j]=='X':\n",
    "                j+=1\n",
    "            if i<n and j<n:\n",
    "                if start[i]!=end[j]:\n",
    "                    return False\n",
    "                ch = start[i]\n",
    "                if (ch==\"L\" and i<j) or (ch==\"R\" and i>j):\n",
    "                    return False\n",
    "                i+=1\n",
    "                j+=1\n",
    "        while i<n:\n",
    "            if start[i]!=\"X\":\n",
    "                return False\n",
    "            i+=1\n",
    "        while j<n:\n",
    "            if end[j]!=\"X\":\n",
    "                return False\n",
    "            j+=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i < n and j < n:\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                c = start[i]\n",
    "                if c == 'L' and i < j or c == 'R' and i > j:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "        while i < n:\n",
    "            if start[i] != 'X':\n",
    "                return False\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            if end[j] != 'X':\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        s, e = start, end\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        while i < n:\n",
    "            if s[i] == 'R':\n",
    "                if j == n:\n",
    "                    return False\n",
    "\n",
    "                j = max(j, i)\n",
    "                while j < n - 1 and e[j] == 'X':\n",
    "                    if s[i] == 'L':\n",
    "                        return False\n",
    "                    j += 1\n",
    "            \n",
    "                if e[j] == 'R':\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            elif i == j and e[j] == 'R':\n",
    "                    return False\n",
    "            i += 1\n",
    "\n",
    "        i, j = n - 1, n - 1\n",
    "        while i >= 0 :\n",
    "            if s[i] == 'L':\n",
    "                if j < 0:\n",
    "                    return False\n",
    "\n",
    "                j = min(j, i)\n",
    "                while j > 0 and e[j] == 'X':\n",
    "                    if s[i] == 'R':\n",
    "                        return False\n",
    "                    j -= 1\n",
    "                    \n",
    "                if e[j] == 'L':\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            elif i == j and e[j] == 'L':\n",
    "                    return False\n",
    "            i -= 1\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1.在去除所有X后，start和end必须相同 注意观察start的L可以一直往左移动，直到遇见R；\n",
    "#     R可以一直往右移动，直到遇见L 比如XXXXXL可以变化为LXXXXX，XRXXXL可以变化为XRLXXX和XXXXRL 所以去除X后，start和end中L和R的顺序必须相同\n",
    "# 2.start中每个L的位置必须在end中对应L的右边，R反之亦然 很好理解，\n",
    "#     比如XXXXXL可以变化为LXXXXX，但是反过来，LXXXXX无法变为XXXXXL\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        i, j = 0, 0\n",
    "        m, n = len(start), len(end)\n",
    "        while i < m and j < n:\n",
    "            while i < m and start[i] == \"X\":\n",
    "                i += 1\n",
    "            while j < n and end[j] == \"X\":\n",
    "                j += 1\n",
    "            if i >= m or j >= n:\n",
    "                break\n",
    "            if start[i] != end[j]:\n",
    "                return False\n",
    "            if start[i] == \"L\" and i < j:\n",
    "                return False\n",
    "            if start[i] == \"R\" and i > j:\n",
    "                return False\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        while i < m:\n",
    "            if start[i] != \"X\":\n",
    "                return False\n",
    "            i += 1\n",
    "\n",
    "        while j < n:\n",
    "            if end[j] != \"X\":\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1.在去除所有X后，start和end必须相同 注意观察start的L可以一直往左移动，直到遇见R；\n",
    "#     R可以一直往右移动，直到遇见L 比如XXXXXL可以变化为LXXXXX，XRXXXL可以变化为XRLXXX和XXXXRL 所以去除X后，start和end中L和R的顺序必须相同\n",
    "# 2.start中每个L的位置必须在end中对应L的右边，R反之亦然 很好理解，\n",
    "#     比如XXXXXL可以变化为LXXXXX，但是反过来，LXXXXX无法变为XXXXXL\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i, j = 0, 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == \"X\":\n",
    "                i += 1\n",
    "            while j < n and end[j] == \"X\":\n",
    "                j += 1\n",
    "            if i < n and j < n:\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                if start[i] == \"L\" and i < j:\n",
    "                    return False\n",
    "                if start[i] == \"R\" and i > j:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "        while i < n:\n",
    "            if start[i] != \"X\":\n",
    "                return False\n",
    "            i += 1\n",
    "\n",
    "        while j < n:\n",
    "            if end[j] != \"X\":\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        if start.replace('X', '') != end.replace('X', ''):\n",
    "            return False\n",
    "        sl, el = 0, 0\n",
    "        sr, er = 0, 0\n",
    "        for sch, ech in zip(start, end):\n",
    "            if sch == 'L':\n",
    "                sl += 1\n",
    "            elif sch == 'R':\n",
    "                sr += 1\n",
    "            if ech == 'L':\n",
    "                el += 1\n",
    "            elif ech == 'R':\n",
    "                er += 1\n",
    "            if sl > el or sr < er:\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        # L 能往左移\n",
    "        # R 能往右移\n",
    "\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "\n",
    "        while i < len(start) or j < len(end):\n",
    "            while i < len(start) and start[i] == 'X':\n",
    "                i += 1\n",
    "            \n",
    "            while j < len(end) and end[j] == 'X':\n",
    "                j += 1\n",
    "            \n",
    "            if i < len(start) and j < len(end):\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                elif start[i] == 'L':\n",
    "                    if i < j:\n",
    "                        return False\n",
    "                elif start[i] == 'R':\n",
    "                    if i > j:\n",
    "                        return False\n",
    "                \n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif i == len(start) and j == len(end):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while 1:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i >= n and j >= n:\n",
    "                return True\n",
    "            if i >= n or j >= n or start[i] != end[j]:\n",
    "                return False\n",
    "            if start[i] == 'L' and i < j:\n",
    "                return False\n",
    "            if start[i] == 'R' and i > j:\n",
    "                return False\n",
    "            i, j = i + 1, j + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start.replace('X', '') != end.replace('X', ''):\n",
    "            return False\n",
    "        n = len(start)\n",
    "        j = 0\n",
    "        for i, ch in enumerate(end):\n",
    "            if ch == 'X':\n",
    "                continue\n",
    "            elif ch == 'R':\n",
    "                while i > j and start[j] != ch:\n",
    "                    if start[j] == 'L':\n",
    "                        return False\n",
    "                    else:\n",
    "                        j += 1\n",
    "                if start[j] == ch:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                while j < n and start[j] != ch:\n",
    "                    if start[j] == 'R':\n",
    "                        return False\n",
    "                    else:\n",
    "                        j += 1\n",
    "                if i <= j and j < n and start[j] == ch:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        idx1, idx2 = 0, 0\n",
    "        while idx1 < n and idx2 < n:\n",
    "            while idx1 < n and start[idx1] == \"X\":\n",
    "                idx1 += 1\n",
    "            while idx2 < n and end[idx2] == \"X\":\n",
    "                idx2 += 1\n",
    "            if idx1 < n and idx2 < n:\n",
    "                if start[idx1] != end[idx2]:\n",
    "                    return False\n",
    "                if start[idx1] == \"L\" and idx1 < idx2 or start[idx1] == \"R\" and idx1 > idx2:\n",
    "                    return False\n",
    "                idx1 += 1\n",
    "                idx2 += 1\n",
    "        while idx1 < n:\n",
    "            if start[idx1] != \"X\":\n",
    "                return False\n",
    "            idx1 += 1\n",
    "        while idx2 < n:\n",
    "            if end[idx2] != \"X\":\n",
    "                return False\n",
    "            idx2 += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i < n and j < n:\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                c = start[i]\n",
    "                if c == 'L' and i < j or c == 'R' and i > j:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "        while i < n:\n",
    "            if start[i] != 'X':\n",
    "                return False\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            if end[j] != 'X':\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        sCounter = Counter(start)\n",
    "        eCounter = Counter(end)\n",
    "        for c in ['R', 'L', 'X']:\n",
    "            if sCounter[c] != eCounter[c]:\n",
    "                return False\n",
    "        n = len(start)\n",
    "        j = 0\n",
    "        # start的L只能往左走，R只能往右走\n",
    "        for i in range(n):\n",
    "            if start[i] == 'X':\n",
    "                continue\n",
    "            while j < n:\n",
    "                if end[j] != 'X':\n",
    "                    break\n",
    "                j += 1\n",
    "            if j == n or start[i] != end[j]: # 第一个碰到的非X是相等的\n",
    "                return False\n",
    "            if start[i] == 'L' and i < j:\n",
    "                return False\n",
    "            if start[i] == 'R' and i > j:\n",
    "                return False\n",
    "            j += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canTransform(self, start: str, end: str) -> bool:\r\n",
    "        L=len(start)\r\n",
    "        i=j=0\r\n",
    "        while i<L and j<L:\r\n",
    "            while i<L and start[i]=='X':\r\n",
    "                i+=1\r\n",
    "            while j<L and end[j]=='X':\r\n",
    "                j+=1\r\n",
    "            if i==L or j==L:\r\n",
    "                break\r\n",
    "            if start[i]==end[j]:\r\n",
    "                if (start[i]=='L' and i>=j) or (start[i]=='R' and i<=j):\r\n",
    "                    i+=1\r\n",
    "                    j+=1\r\n",
    "                    continue\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return False\r\n",
    "        if i==L:\r\n",
    "            return all(end[n]=='X' for n in range(j,L))\r\n",
    "        if j==L:\r\n",
    "            return all(start[n]=='X' for n in range(i,L))\r\n",
    "        # return True\r\n",
    "\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, target: str) -> bool:\n",
    "        s, t = start.replace('X', \"\"), target.replace('X', \"\")\n",
    "        if s != t: return False\n",
    "        j = 0\n",
    "        for i in range(len(start)):\n",
    "            if start[i] == 'X': continue\n",
    "            while target[j] == 'X': j += 1\n",
    "            if start[i] == 'L' and i < j: return False\n",
    "            if start[i] == 'R' and i > j: return False\n",
    "            j += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i, j = 0, 0\n",
    "        while i < n or j < n:\n",
    "            while i < n and start[i] == 'X': i += 1\n",
    "            while j < n and end[j] == 'X': j += 1\n",
    "            if i == n or j == n: return i == j\n",
    "\n",
    "            if start[i] != end[j]: return False\n",
    "            if start[i] == 'L' and i < j: return False\n",
    "            if start[i] == 'R' and i > j: return False\n",
    "            i += 1\n",
    "            j += 1\n",
    "        return i == j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i = j = 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "            if i < n and j < n:\n",
    "                if start[i] != end[j]:\n",
    "                    return False\n",
    "                c = start[i]\n",
    "                if c == 'L' and i < j or c == 'R' and i > j:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "        while i < n:\n",
    "            if start[i] != 'X':\n",
    "                return False\n",
    "            i += 1\n",
    "        while j < n:\n",
    "            if end[j] != 'X':\n",
    "                return False\n",
    "            j += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start.replace('X', '') != end.replace('X', ''):\n",
    "            return False\n",
    "\n",
    "        n = len(start)\n",
    "        i, j = 0, 0\n",
    "        while i < n and j < n:\n",
    "            while i < n and start[i] == 'X':\n",
    "                i += 1\n",
    "            while j < n and end[j] == 'X':\n",
    "                j += 1\n",
    "\n",
    "            if i == n and j == n:\n",
    "                return True\n",
    "\n",
    "            if (i == n) != (j == n):\n",
    "                return False\n",
    "\n",
    "            if start[i] != end[j]:\n",
    "                return False\n",
    "\n",
    "            if start[i] == 'L' and i < j:\n",
    "                return False\n",
    "\n",
    "            if start[i] == 'R' and i > j:\n",
    "                return False\n",
    "\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start.replace('X', '') != end.replace('X', ''):\n",
    "            return False\n",
    "        \n",
    "        j = 0\n",
    "        for i, c in enumerate(start):\n",
    "            if c == 'X': continue\n",
    "            while end[j] == 'X':\n",
    "                j += 1\n",
    "            if (i != j) and ((i < j) == (c == 'L')):\n",
    "                return False\n",
    "            j += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canTransform(self, start: str, end: str) -> bool:\r\n",
    "        # 和2337一样\r\n",
    "        if start.replace('X','') != end.replace('X',''):\r\n",
    "            return False\r\n",
    "        j = 0\r\n",
    "        for i,v in enumerate(start):\r\n",
    "            if v == 'X':\r\n",
    "                continue\r\n",
    "            while end[j] == 'X':\r\n",
    "                j += 1\r\n",
    "            if i < j and end[j] == 'L':\r\n",
    "                return False\r\n",
    "            if i > j and end[j] == 'R':\r\n",
    "                return False\r\n",
    "            j += 1\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start.replace('X', '') != end.replace('X', ''):\n",
    "            return False\n",
    "        \n",
    "        p1, p2 = 0, 0\n",
    "        while p1 < len(start) and p2 < len(end):\n",
    "            while p1 < len(start) and start[p1] == 'X':\n",
    "                p1 += 1\n",
    "            \n",
    "            while p2 < len(end) and end[p2] == 'X':\n",
    "                p2 += 1\n",
    "            \n",
    "            if (p1 == len(start)) != (p2 == len(end)):\n",
    "                return False\n",
    "            \n",
    "            if p1 < len(start) and p2 < len(end):\n",
    "                if start[p1] == 'L' and (p1 < p2 or end[p2] != 'L'):\n",
    "                    return False\n",
    "                \n",
    "                if start[p1] == 'R' and (p1 > p2 or end[p2] != 'R'):\n",
    "                    return False\n",
    "            \n",
    "            p1 += 1\n",
    "            p2 += 1\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        i=j=0\n",
    "        while i<n and j<n:\n",
    "            while i<n and start[i]=='X':\n",
    "                i+=1\n",
    "            while j<n and end[j]=='X':\n",
    "                j+=1\n",
    "            if i<n and j<n:\n",
    "                if start[i]!=end[j]:\n",
    "                    return False\n",
    "                ch = start[i]\n",
    "                if (ch==\"L\" and i<j) or (ch==\"R\" and i>j):\n",
    "                    return False\n",
    "                i+=1\n",
    "                j+=1\n",
    "        while i<n:\n",
    "            if start[i]!=\"X\":\n",
    "                return False\n",
    "            i+=1\n",
    "        while j<n:\n",
    "            if end[j]!=\"X\":\n",
    "                return False\n",
    "            j+=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        i, j = 0, 0\n",
    "        while j < len(end):\n",
    "            if end[j] == \"R\":\n",
    "                while i < len(start):\n",
    "                    if start[i] == \"L\":\n",
    "                        return False\n",
    "                    if start[i] == \"R\" and i > j:\n",
    "                        return False \n",
    "                    if start[i] == \"R\" and i <= j:\n",
    "                        break\n",
    "                    i += 1\n",
    "                if i == len(start):\n",
    "                    return False\n",
    "                i += 1 \n",
    "            elif end[j] == \"L\":\n",
    "                while i < len(start):\n",
    "                    if start[i] == \"R\":\n",
    "                        return False\n",
    "                    if start[i] == \"L\" and i < j:\n",
    "                        return False\n",
    "                    if start[i] == \"L\" and i >= j:\n",
    "                        break\n",
    "                    i += 1\n",
    "                if i == len(start):\n",
    "                    return False\n",
    "                i += 1\n",
    "            j += 1\n",
    "        for x in range(i, len(start)):\n",
    "            if start[x] != \"X\":\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        n = len(start)\n",
    "        #check R\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            c1 = start[i]\n",
    "            c2 = end[i]\n",
    "            if(c1 == 'R'):\n",
    "                cnt1 += 1\n",
    "            if(c2 == 'R'):\n",
    "                cnt2 += 1\n",
    "            if(c2 == 'L'):\n",
    "                if(cnt1 != cnt2):\n",
    "                    return False\n",
    "            if(c1 == 'L'):\n",
    "                if(cnt1 != cnt2):\n",
    "                    return False\n",
    "            if(cnt1 < cnt2):\n",
    "                return False\n",
    "        if(cnt1 != cnt2):\n",
    "            return False\n",
    "        #check L\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            c1 = start[i]\n",
    "            c2 = end[i]\n",
    "            if(c1 == 'L'):\n",
    "                cnt1 += 1\n",
    "            if(c2 == 'L'):\n",
    "                cnt2 += 1\n",
    "            if(c2 == 'R'):\n",
    "                if(cnt1 != cnt2):\n",
    "                    return False\n",
    "            if(c1 == 'R'):\n",
    "                if(cnt1 != cnt2):\n",
    "                    return False\n",
    "            if(cnt1 < cnt2):\n",
    "                return False\n",
    "        if(cnt1 != cnt2):\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start.replace('X','') != end.replace('X',''):\n",
    "            return False\n",
    "        j = 0\n",
    "        for i,x in enumerate(start):\n",
    "            if x == 'X':\n",
    "                continue\n",
    "            while end[j] == 'X':\n",
    "                j += 1\n",
    "            if i < j and x == 'L':\n",
    "                return False\n",
    "            if i > j and x == 'R':\n",
    "                return False\n",
    "            j += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, target: str) -> bool:\n",
    "        l, r = 0, 0\n",
    "        n = len(start)\n",
    "        while l != n and r != n:\n",
    "            if start[l] == \"X\":\n",
    "                l += 1\n",
    "            elif target[r] == \"X\":\n",
    "                r += 1\n",
    "            elif target[r] == start[l] and target[r] == \"L\":\n",
    "                if l < r:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r += 1\n",
    "            elif target[r] == start[l] and target[r] == \"R\":\n",
    "                if l > r:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r += 1\n",
    "            else:\n",
    "                return False\n",
    "        while l != n:\n",
    "            if start[l] != \"X\":\n",
    "                return False\n",
    "            l += 1\n",
    "        while r != n:\n",
    "            if target[r] != \"X\":\n",
    "                return False\n",
    "            r += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canTransform(self, start: str, end: str) -> bool:\r\n",
    "        L=len(start)\r\n",
    "        i=j=0\r\n",
    "        while i<L and j<L:\r\n",
    "            while i<L and start[i]=='X':\r\n",
    "                i+=1\r\n",
    "            while j<L and end[j]=='X':\r\n",
    "                j+=1\r\n",
    "            if i==L or j==L:\r\n",
    "                break\r\n",
    "            if start[i]==end[j]:\r\n",
    "                if (start[i]=='L' and i>=j) or (start[i]=='R' and i<=j):\r\n",
    "                    i+=1\r\n",
    "                    j+=1\r\n",
    "                    continue\r\n",
    "                return False\r\n",
    "            else:\r\n",
    "                return False\r\n",
    "        while i<L:\r\n",
    "            if start[i]!='X':\r\n",
    "                return False\r\n",
    "            i+=1\r\n",
    "        \r\n",
    "        while j<L:\r\n",
    "            if end[j]!='X':\r\n",
    "                return False\r\n",
    "            j+=1\r\n",
    "        return True\r\n",
    "\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if start==end:\n",
    "            return True\n",
    "        R=[]\n",
    "        L=[]\n",
    "        ri=0\n",
    "        li=0\n",
    "        for i in range(len(end)):\n",
    "            if end[i]==\"R\":\n",
    "                R.append(i)\n",
    "            elif end[i]==\"L\":\n",
    "                L.append(i)\n",
    "        i=0\n",
    "      \n",
    "      \n",
    "        while i<len(start):\n",
    "           \n",
    "            if start[i]==\"X\":\n",
    "                i+=1\n",
    "                continue\n",
    "            if start[i]==\"R\":\n",
    "                if ri>=len(R):\n",
    "                    return False\n",
    "                if i>R[ri]:\n",
    "                    return False\n",
    "                if i==R[ri]:\n",
    "                    i+=1\n",
    "                    ri+=1\n",
    "                    continue\n",
    "                for j in range(i+1,R[ri]+1):\n",
    "                    if start[j]==\"L\":\n",
    "                        return False\n",
    "                i+=1\n",
    "                ri+=1\n",
    "                continue\n",
    "            if start[i]==\"L\":\n",
    "                if li>=len(L):\n",
    "                    return False\n",
    "                if i<L[li]:\n",
    "                    return False\n",
    "                if i==L[li]:\n",
    "                    i+=1\n",
    "                    li+=1\n",
    "                    continue\n",
    "                for j in range(i-1,L[li]-1,-1):\n",
    "                    if start[j]==\"R\":\n",
    "                        \n",
    "                        return False\n",
    "                i+=1\n",
    "                li+=1\n",
    "                continue\n",
    "        \n",
    "        if li!=len(L) or ri!=len(R):\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        # 被替换项- XL | RX\n",
    "        # print(\"\".join(start.split('X')), \"\".join(end.split('X')))\n",
    "        # return \"\".join(start.split('X')) == \"\".join(end.split('X'))\n",
    "        # L可以往左边所有空位(X)上交换 R可以往右边所有空位(X)上交换\n",
    "        # for i,x in enumerate(start):\n",
    "        #     if end\n",
    "        #     if x == \"X\":\n",
    "        #         res.add(i)\n",
    "        #     elif x == \"L\":\n",
    "        # 先记录end 的 L R 的位置 再在 start 中一步步替换\n",
    "        if \"\".join(start.split('X')) != \"\".join(end.split('X')): return False\n",
    "        n = len(start)\n",
    "        j = 0\n",
    "        # start, end = list(start), list(end)\n",
    "        for i, x in enumerate(end):\n",
    "            if x == \"L\":\n",
    "                j = start.find(x, j, n)\n",
    "                s = j\n",
    "                if j < i: return False\n",
    "                while j > i and start[j-1] in [\"X\", \"L\"]:\n",
    "                    j -= 1\n",
    "                if start[j] not in [\"X\", \"L\"]: return False\n",
    "                j = s+1\n",
    "        j = n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if end[i] == \"R\":\n",
    "                j = start.rfind(end[i], 0, j)\n",
    "                s = j\n",
    "                if j > i: return False\n",
    "                while j < i and start[j+1] in [\"X\", \"R\"]:\n",
    "                    j += 1\n",
    "                if start[j] not in [\"X\", \"R\"]: return False\n",
    "                j = s\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        if len(start) != len(end):\n",
    "            return False\n",
    "        if start == end:\n",
    "            return True\n",
    "        start_list = list(start)\n",
    "        end_list = list(end)\n",
    "        i = 0\n",
    "        n = len(start_list)\n",
    "        while i < n:\n",
    "            if start_list[i] == end_list[i]:\n",
    "                i += 1\n",
    "                continue\n",
    "            if i == n - 1:\n",
    "                return False\n",
    "            if end_list[i] == \"L\":\n",
    "                j = i\n",
    "                while j < n and start_list[j] == \"X\":\n",
    "                    j += 1\n",
    "                if j == n or start_list[j] == \"R\":\n",
    "                    return False\n",
    "\n",
    "                start_list[i], start_list[j] = start_list[j], start_list[i]\n",
    "                i += 1\n",
    "            elif end_list[i] == \"R\":\n",
    "                return False\n",
    "            else:  # end_list[i] == 'X'\n",
    "                j = i\n",
    "                while j < n and start_list[j] == \"R\":\n",
    "                    j += 1\n",
    "                if j == n or start_list[j] == \"L\":\n",
    "                    return False\n",
    "\n",
    "                start_list[i], start_list[j] = start_list[j], start_list[i]\n",
    "                i += 1\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert Solution().canTransform(\"RXXLRXRXL\", \"XRLXXRRLX\")\n",
    "    # assert not Solution().canTransform(\"RL\", \"LR\")\n",
    "    # assert Solution().canTransform(\"XXXXXLXXXX\", \"LXXXXXXXXX\")\n",
    "    # assert Solution().canTransform(\"XLXRRXXRXX\", \"LXXXXXXRRR\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        idx = []\n",
    "        n = len(start)\n",
    "        for i in range(n):\n",
    "            if end[i] != 'X':\n",
    "                idx.append(i)\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            if start[i] != 'X':\n",
    "                if j >= len(idx):\n",
    "                    return False\n",
    "                if start[i] != end[idx[j]] or start[i] == 'L' and idx[j] > i\\\n",
    "                or start[i] == 'R' and idx[j] < i:\n",
    "                    return False\n",
    "                j += 1\n",
    "        return j == len(idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        ds,de = 0,0\n",
    "        ca,cb = 0,0\n",
    "        while de < len(end):\n",
    "            if end[de] == 'X':\n",
    "                de += 1\n",
    "                cb += 1\n",
    "                continue\n",
    "            f = False\n",
    "            while ds < len(start):\n",
    "                if start[ds] == 'X':\n",
    "                    ds += 1\n",
    "                    ca += 1\n",
    "                    continue\n",
    "                if start[ds] == end[de]:\n",
    "                    if start[ds] == 'L':\n",
    "                        if ca >= cb:\n",
    "                            f = True\n",
    "                    if start[ds] == 'R':\n",
    "                        if ca <= cb:\n",
    "                            f = True\n",
    "                    ca,cb = ca-cb,0\n",
    "                    ds += 1\n",
    "                break\n",
    "            de += 1\n",
    "            if not f:\n",
    "                return False\n",
    "        return all(start[ds] == 'X' for ds in range(ds,len(start)))\n",
    "        #return True\n",
    "s = Solution()\n",
    "s.canTransform(\"RXXLRXRXL\",\"XRLXXRRLX\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        s = []\n",
    "        Ls = []\n",
    "        Rs = []\n",
    "        for i in range(len(start)):\n",
    "            if start[i]!='X':\n",
    "                s.append(start[i])\n",
    "            if  start[i] == 'L':\n",
    "                Ls.append(i)\n",
    "            elif start[i] == 'R':\n",
    "                Rs.append(i)\n",
    "        e = []\n",
    "        Le = []\n",
    "        Re = []\n",
    "        for i in range(len(end)):\n",
    "            if end[i]!='X':\n",
    "                e.append(end[i])\n",
    "            if  end[i] == 'L':\n",
    "                Le.append(i)\n",
    "            elif end[i] == 'R':\n",
    "                Re.append(i)\n",
    "        if (len(Ls)!=len(Le)) or (len(Rs)!=len(Re)) :\n",
    "            return False\n",
    "        else:\n",
    "            for i in range(len(s)):\n",
    "                if s[i]!=e[i]:\n",
    "                    return False\n",
    "            for i in range(len(Ls)):\n",
    "                if Ls[i]<Le[i]:\n",
    "                    return False\n",
    "            for i in range(len(Rs)):\n",
    "                if Rs[i]>Re[i]:\n",
    "                    return False\n",
    "            # for i in range(0,len(start),2):\n",
    "            #     if (i+2<=len(start)) and ((start[i:i+2]==\"LX\" and end[i:i+2] == \"XL\") or (start[i:i+2]==\"XR\" and end[i:i+2] == \"RX\")):\n",
    "            #         return False\n",
    "            # for i in range(1,len(start),2):\n",
    "            #     if (i+2<=len(start)) and ((start[i:i+2]==\"LX\" and end[i:i+2] == \"XL\") or (start[i:i+2]==\"XR\" and end[i:i+2] == \"RX\")):\n",
    "            #         return False\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        #三个条件：数量次序对，start的L出现更晚，R出现更早\n",
    "        def wash(x):\n",
    "            m = \"\"\n",
    "            for i in x:\n",
    "                if i == \"R\" or i == \"L\":\n",
    "                    m +=i\n",
    "            return m\n",
    "        if wash(start) != wash(end): \n",
    "            return False\n",
    "        \n",
    "        def f(x):\n",
    "            n = [[],[]]\n",
    "            le = len(x)\n",
    "            for i in range(le):\n",
    "                if x[i]==\"R\":\n",
    "                    n[0]+=[i]\n",
    "                elif x[i]==\"L\":\n",
    "                    n[1]+=[i]\n",
    "            return n\n",
    "        a = f(start)\n",
    "        b = f(end)\n",
    "        lr = len(a[0])\n",
    "        ll = len(a[1])\n",
    "        #print(wash(start),a,b)  \n",
    "        for i in range(lr):\n",
    "            if a[0][i] > b[0][i]:\n",
    "                return False\n",
    "        for i in range(ll):\n",
    "            if a[1][i] < b[1][i]:\n",
    "                return False         \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        st = collections.deque()\n",
    "        for i,ch in enumerate(start):\n",
    "            if ch!=\"X\":\n",
    "                st.append([ch,i])\n",
    "        for i,ch in enumerate(end):\n",
    "            if ch!=\"X\":\n",
    "                if not st:\n",
    "                    return False\n",
    "                if ch!=st[0][0] or (ch==\"R\" and st[0][1]>i) or (ch==\"L\" and st[0][1]<i):\n",
    "                    return False\n",
    "                else:\n",
    "                    st.popleft()\n",
    "        if st:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        l, r = [], []\n",
    "        for i, c in enumerate(start):\n",
    "            if c == 'L':\n",
    "                l.append(i)\n",
    "            elif c == 'R':\n",
    "                r.append(i)\n",
    "        nl, nr = [], []\n",
    "        for i, c in enumerate(end):\n",
    "            if c == 'L':\n",
    "                nl.append(i)\n",
    "            elif c == 'R':\n",
    "                nr.append(i)\n",
    "\n",
    "        if len(l) != len(nl) or len(r) != len(nr): return False\n",
    "\n",
    "\n",
    "        for i in range(len(l)):\n",
    "            if nl[i] > l[i]: return False\n",
    "        \n",
    "        for i in range(len(r)):\n",
    "            if nr[i] < r[i]: return False\n",
    "\n",
    "        for i in range(len(r)):\n",
    "            for j in range(r[i], nr[i]+1):\n",
    "                if start[j] == 'L' or end[j] == 'L': return False\n",
    "\n",
    "        for i in range(len(l)):\n",
    "            for j in range(nl[i], l[i]+1):\n",
    "                if start[j] == 'R' or end[j] == 'R': return False\n",
    "\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        def wash(x):\n",
    "            m = \"\"\n",
    "            for i in x:\n",
    "                if i == \"R\" or i == \"L\":\n",
    "                    m +=i\n",
    "            return m\n",
    "        if wash(start) != wash(end): \n",
    "            return False\n",
    "        \n",
    "        def f(x):\n",
    "            n = [[],[]]\n",
    "            le = len(x)\n",
    "            for i in range(le):\n",
    "                if x[i]==\"R\":\n",
    "                    n[0]+=[i]\n",
    "                elif x[i]==\"L\":\n",
    "                    n[1]+=[i]\n",
    "            return n\n",
    "        a = f(start)\n",
    "        b = f(end)\n",
    "        lr = len(a[0])\n",
    "        ll = len(a[1])\n",
    "        #print(wash(start),a,b)  \n",
    "        for i in range(lr):\n",
    "            if a[0][i] > b[0][i]:\n",
    "                return False\n",
    "        for i in range(ll):\n",
    "            if a[1][i] < b[1][i]:\n",
    "                return False         \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canTransform(self, start: str, end: str) -> bool:\n",
    "        st = collections.deque()\n",
    "        for i,ch in enumerate(start):\n",
    "            if ch!=\"X\":\n",
    "                st.append([ch,i])\n",
    "        for i,ch in enumerate(end):\n",
    "            if ch!=\"X\":\n",
    "                if not st:\n",
    "                    return False\n",
    "                if ch!=st[0][0] or (ch==\"R\" and st[0][1]>i) or (ch==\"L\" and st[0][1]<i):\n",
    "                    return False\n",
    "                else:\n",
    "                    st.popleft()\n",
    "        if st:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
